{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Difference in Sums After Removal of Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除元素后和的最小差值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，它包含&nbsp;<code>3 * n</code>&nbsp;个元素。</p>\n",
    "\n",
    "<p>你可以从 <code>nums</code>&nbsp;中删除 <strong>恰好</strong>&nbsp;<code>n</code>&nbsp;个元素，剩下的 <code>2 * n</code>&nbsp;个元素将会被分成两个 <strong>相同大小</strong>&nbsp;的部分。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>前面&nbsp;<code>n</code>&nbsp;个元素属于第一部分，它们的和记为&nbsp;<code>sum<sub>first</sub></code>&nbsp;。</li>\n",
    "\t<li>后面&nbsp;<code>n</code>&nbsp;个元素属于第二部分，它们的和记为&nbsp;<code>sum<sub>second</sub></code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>两部分和的 <strong>差值</strong>&nbsp;记为&nbsp;<code>sum<sub>first</sub> - sum<sub>second</sub></code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>sum<sub>first</sub> = 3</code> 且&nbsp;<code>sum<sub>second</sub> = 2</code>&nbsp;，它们的差值为&nbsp;<code>1</code>&nbsp;。</li>\n",
    "\t<li>再比方，<code>sum<sub>first</sub> = 2</code> 且&nbsp;<code>sum<sub>second</sub> = 3</code>&nbsp;，它们的差值为&nbsp;<code>-1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回删除 <code>n</code>&nbsp;个元素之后，剩下两部分和的 <strong>差值的最小值</strong>&nbsp;是多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,1,2]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>nums 有 3 个元素，所以 n = 1 。\n",
    "所以我们需要从 nums 中删除 1 个元素，并将剩下的元素分成两部分。\n",
    "- 如果我们删除 nums[0] = 3 ，数组变为 [1,2] 。两部分和的差值为 1 - 2 = -1 。\n",
    "- 如果我们删除 nums[1] = 1 ，数组变为 [3,2] 。两部分和的差值为 3 - 2 = 1 。\n",
    "- 如果我们删除 nums[2] = 2 ，数组变为 [3,1] 。两部分和的差值为 3 - 1 = 2 。\n",
    "两部分和的最小差值为 min(-1,1,2) = -1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [7,9,5,8,1,3]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>n = 2 。所以我们需要删除 2 个元素，并将剩下元素分为 2 部分。\n",
    "如果我们删除元素 nums[2] = 5 和 nums[3] = 8 ，剩下元素为 [7,9,1,3] 。和的差值为 (7+9) - (1+3) = 12 。\n",
    "为了得到最小差值，我们应该删除 nums[1] = 9 和 nums[4] = 1 ，剩下的元素为 [7,5,8,3] 。和的差值为 (7+5) - (8+3) = 1 。\n",
    "观察可知，最优答案为 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length == 3 * n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-difference-in-sums-after-removal-of-elements](https://leetcode.cn/problems/minimum-difference-in-sums-after-removal-of-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-difference-in-sums-after-removal-of-elements](https://leetcode.cn/problems/minimum-difference-in-sums-after-removal-of-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,2]', '[7,9,5,8,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if k >= n:\n",
    "            return nums[-1]-nums[0]\n",
    "        ans = math.inf\n",
    "        for i in range(n-k+1):\n",
    "            ans = min(ans,nums[i+k-1]-nums[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        \n",
    "        res = 100001\n",
    "        nums.sort()\n",
    "\n",
    "        for i in range(len(nums)-k+1):\n",
    "            res = min(res, nums[i+k-1]-nums[i])\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i+k-1]-nums[i] for i in range(len(nums)-k+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = float('inf')\n",
    "        for i in range(len(nums)- k + 1):\n",
    "            check = nums[i:i+k]\n",
    "            res = min(res,max(check)-min(check))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 100000\n",
    "        for i in range(k-1, len(nums)):\n",
    "            if nums[i] - nums[i-k+1] < ans:\n",
    "                ans = nums[i] - nums[i-k+1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if nums == [] or len(nums) == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        result = 99999999 #max num\n",
    "        leftPtr = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i >= k - 1:\n",
    "                if result > nums[i] - nums[leftPtr]:\n",
    "                    result = nums[i] - nums[leftPtr]\n",
    "                leftPtr += 1\n",
    "\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums_len=len(nums)\n",
    "        nums.sort()\n",
    "        ans = float('inf')\n",
    "        for i in range(k-1,nums_len):\n",
    "            ans=min(ans,nums[i]-nums[i-k+1])\n",
    "            if ans==0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        # 开头k个数\n",
    "        ans = nums[k-1] - nums[0]\n",
    "        for right,num in enumerate(nums[k:],k):\n",
    "            ans = min(ans,num - nums[right-k+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        nums = sorted(nums)\n",
    "        Min = 100001\n",
    "        for i in range(len(nums)-k+1):\n",
    "            Min = min(Min, nums[i+k-1] - nums[i])\n",
    "        return Min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        k -= 1\n",
    "        return min(nums[i+k] - nums[i] for i in range(len(nums)-k))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for i in range(n-k+1):\n",
    "            res = min(res,nums[i+k-1]-nums[i])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        # 我的解法 排序+固定值滑动窗口\n",
    "        nums.sort()\n",
    "        # n = len(nums)\n",
    "        # left = 0\n",
    "        # right = left + k - 1\n",
    "        # mindic = inf\n",
    "        # while right < n:\n",
    "        #     mindic = min(mindic, nums[right]-nums[left])\n",
    "        #     left += 1\n",
    "        #     right += 1\n",
    "        # return mindic\n",
    "\n",
    "        # 代码简化\n",
    "        return min(nums[i + k -1] - nums[i] for i in range(len(nums) - k + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[k-1] - nums[0]\n",
    "        for right, num in enumerate(nums[k:], k):\n",
    "            ans = min(ans, num-nums[right-k+1])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1 or len(nums) == 1:\n",
    "            return 0\n",
    "        nums.sort(reverse = True)\n",
    "        min_res = 100000\n",
    "        for i in range(len(nums)-k+1):\n",
    "            tem = nums[i] - nums[i+k-1]\n",
    "            if tem<min_res:\n",
    "                min_res = tem\n",
    "        return min_res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        # nums=sorted(nums)\n",
    "        res=float(\"inf\")\n",
    "        for i in range(n-k+1):\n",
    "            value=nums[i+k-1]-nums[i]\n",
    "            res=min(res,value)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        思路：\n",
    "        \"\"\"\n",
    "        sort_nums = sorted(nums)\n",
    "        if len(sort_nums) < 2:\n",
    "            return 0\n",
    "        diff_list = []\n",
    "        for i in range(len(sort_nums)):\n",
    "            if i + k - 1 < len(sort_nums):\n",
    "                diff = sort_nums[i+k-1] - sort_nums[i]\n",
    "                diff_list.append(diff)\n",
    "\n",
    "        return min(diff_list)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        n = len(nums)\n",
    "        for i in range(n - k + 1):\n",
    "            ans = min(nums[i + k - 1] - nums[i], ans)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        mins=math.inf\n",
    "        for i in range(len(nums)):\n",
    "            if i+k<=len(nums):\n",
    "                mins=min(mins,max(nums[i:i+k])-min(nums[i:i+k]))\n",
    "        return mins\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        min = 10000000\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            if nums[i+k-1] - nums[i] < min:\n",
    "                min = nums[i+k-1] - nums[i]\n",
    "        return min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[k-1] - nums[0]\n",
    "        for left in range(len(nums)-k+1):\n",
    "            right = left + k-1\n",
    "            ans = min(nums[right] - nums[left], ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        if n == 1:\r\n",
    "            return 0\r\n",
    "        nums.sort()\r\n",
    "        left = 0\r\n",
    "        ans = inf\r\n",
    "        while left + k - 1 < n:\r\n",
    "            ans = min(ans, nums[left + k - 1] - nums[left])\r\n",
    "            left += 1\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[k-1] - nums[0]\n",
    "        for right, num in enumerate(nums[k:], k):\n",
    "            ans = min(ans, num-nums[right-k+1])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums) == k:\n",
    "            return nums[-1] - nums[0]\n",
    "        mindf = float(\"inf\")\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            if nums[i + k - 1] - nums[i] < mindf:\n",
    "                mindf = nums[i + k - 1] - nums[i]\n",
    "        return mindf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(j-i for i, j in zip(nums, nums[k-1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        if k > 1:\n",
    "            nums = sorted(nums)\n",
    "            min_ = min(nums[i+k-1]-nums[i] for i in range(len(nums)-k+1))\n",
    "            return min_\n",
    "        else:\n",
    "            return 0\n",
    "        \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        res=inf\n",
    "        if k>1:\n",
    "            for i in range(n-k+1):\n",
    "                res=min(res,nums[i+k-1]-nums[i])\n",
    "        else:\n",
    "            res=0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i+k-1]-nums[i] for i in range(len(nums)-k+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#处理序列问题的一些技巧：\n",
    "#观察排序是否影响结果，不影响就可以考虑排序能否降低复杂度\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: list[int], k: int) :\n",
    "        nums.sort()\n",
    "        ans = max(nums)\n",
    "        for right in range(k-1,len(nums)):\n",
    "            left = right - k + 1\n",
    "            ans = min(ans,nums[right] - nums[left])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        res=inf\n",
    "        if k>1:\n",
    "            for i in range(n-k+1):\n",
    "                res=min(res,nums[i+k-1]-nums[i])\n",
    "        else:\n",
    "            res=0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums)<= k:\n",
    "            return max(nums) - min(nums)\n",
    "\n",
    "        nums.sort()\n",
    "        res = math.inf\n",
    "        left , right = 0, k-1\n",
    "        while right < len(nums):\n",
    "            res = min(nums[right] - nums[left],res) \n",
    "            left += 1\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(j-i for i, j in zip(nums, nums[k-1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i+k-1] - nums[i] for i in range(len(nums)-k+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(len(nums)-k+1):\n",
    "            ans = min(ans,nums[i+k-1]-nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[k - 1] - nums[0]\n",
    "        for right, num in enumerate(nums[k:], k):\n",
    "            ans = min(ans, num - nums[right - k + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        # 排序  然后一个k大小的窗口滑动序列  获得最小的极差\n",
    "        nums.sort() \n",
    "        n = len(nums)\n",
    "        ans = 0x3f3f3f3f\n",
    "        for i in range(n-k+1):\n",
    "            ans = min(ans , nums[i+k-1]-nums[i])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        min_val = 1e9\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            min_val = min(min_val, nums[i + k - 1] - nums[i])\n",
    "        return min_val\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        sorted_nums = sorted(nums)\n",
    "        min_diff = sorted_nums[len(sorted_nums) - 1]\n",
    "        for index, num in enumerate(sorted_nums):\n",
    "            if index + k <= len(sorted_nums):\n",
    "                diff = sorted_nums[index + k - 1] - sorted_nums[index]\n",
    "                min_diff = diff if min_diff > diff else min_diff\n",
    "\n",
    "        return min_diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        M = nums[l+k-1] - nums[l]\n",
    "        for i in range(len(nums)-k+1):\n",
    "            l = i\n",
    "            M = min(M, nums[l+k-1] - nums[l])\n",
    "        return M\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if k > n:\n",
    "            return max(nums) - min(nums)\n",
    "\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        l = 0\n",
    "        r = l + k\n",
    "        while r <= n:\n",
    "            window = nums[l:r]\n",
    "            ans = min(ans, max(window) - min(window))\n",
    "            l, r = l + 1, r + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        nums.sort()\r\n",
    "        left = 0\r\n",
    "        ans = inf\r\n",
    "        while left + k - 1 < n:\r\n",
    "            ans = min(ans, nums[left + k - 1] - nums[left])\r\n",
    "            left += 1\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        # nums=sorted(nums)\n",
    "        res=float(\"inf\")\n",
    "        for i in range(n-k+1):\n",
    "            value=nums[i+k-1]-nums[i]\n",
    "            res=min(res,value)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MAX = 100000\n",
    "    def insertSort(self,nums:List[int]):\n",
    "        for i in range(1,len(nums)):\n",
    "            tmp = nums[i]\n",
    "            j = i-1\n",
    "            while j >= 0:\n",
    "                if nums[j] > tmp: nums[j+1] = nums[j]\n",
    "                else: break\n",
    "                j-=1\n",
    "            nums[j+1] = tmp\n",
    "\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        self.insertSort(nums)\n",
    "        l = 0;r = k-1\n",
    "        df_min = Solution.MAX\n",
    "        while r < len(nums):\n",
    "            tmp = nums[r] - nums[l]\n",
    "            df_min = df_min if df_min < tmp else tmp\n",
    "            r+=1;l+=1\n",
    "        return df_min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        res=nums[-1]-nums[0]\n",
    "        while i<len(nums)-k+1:\n",
    "            res=min(res,nums[i+k-1]-nums[i])\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(j-i for i, j in zip(nums, nums[k-1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        ans=99999999\n",
    "        for i in range(len(nums)-k+1):\n",
    "            ans=min(ans,nums[i+k-1]-nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(j-i for i, j in zip(nums, nums[k-1:]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        while i+k<=n:\n",
    "            ans = min(ans,nums[i+k-1]-nums[i])\n",
    "            i+=1\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        ans = 100000\n",
    "        nums.sort(reverse=True)\n",
    "        i = 0\n",
    "        while i + k <= len(nums):\n",
    "            ans = min(ans, nums[i] - nums[i + k - 1])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k==1:\n",
    "            return 0\n",
    "        lt=len(nums)\n",
    "        nums.sort()\n",
    "        ans=[]\n",
    "        flag=nums[-1]-nums[0]\n",
    "        for i in range(k-1,lt):\n",
    "            tflag=nums[i]-nums[i-k+1]\n",
    "            if tflag < flag:\n",
    "                flag = tflag\n",
    "        return flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        gap = []\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(len(nums)-k+1):\n",
    "                gap.append(nums[i+k-1] - nums[i])\n",
    "\n",
    "            gap.sort()\n",
    "            return gap[0]\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()   #首先对数组进行排序，从小到大排序\n",
    "        ans=nums[k-1]-nums[0]  #初始化第一个滑窗为nums[:k],初始化答案变量为滑窗里面最大值和最小值的差值\n",
    "        for right,num in enumerate(nums[k:],k):  #窗口右边界为right,左边界为left\n",
    "            left=right-k+1\n",
    "            ans=min(ans,num-nums[left])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        diff = float('inf')\n",
    "        n = len(nums)\n",
    "        if k == 0 or len(nums) == 1:\n",
    "            return 0\n",
    "        for i in range(n-k+1):\n",
    "            diff = min(diff, nums[i+k-1]-nums[i])\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        a = float('inf')\n",
    "        for i in range(len(nums)-k+1):\n",
    "            a=min(a,nums[i+k-1]-nums[i])\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if k > n:\n",
    "            return max(nums) - min(nums)\n",
    "\n",
    "        nums.sort()  # O(nlogn)\n",
    "        ans = inf\n",
    "        l = 0\n",
    "        r = l + k\n",
    "        while r <= n:  # O(n)\n",
    "            ans = min(ans, nums[r - 1] - nums[l])\n",
    "            l, r = l + 1, r + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        \n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        result = nums[0] +1\n",
    "        \n",
    "        pos = 0\n",
    "        while pos + k <= len(nums):\n",
    "            result = min(result, nums[pos] - nums[pos+k -1])\n",
    "            pos += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def InsertionSort(self,a):\n",
    "        n = len(a)\n",
    "        for i in range(1,n):\n",
    "            x = a[i]\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "                if x > a[j]:\n",
    "                    a[j+1] = a[j]\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    break\n",
    "            a[j+1] = x\n",
    "\n",
    "\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        # self.InsertionSort(nums)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ret = 100000\n",
    "        for i in range(n-k+1):\n",
    "            ans = nums[i+k-1] - nums[i]\n",
    "            if ans < ret:\n",
    "                ret = ans\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1 or k==1 or k>n:\n",
    "            return 0\n",
    "        a,b=0, k-1\n",
    "        nums.sort()\n",
    "        mi = 10000000\n",
    "        while b < n:\n",
    "            mi = min(mi, nums[b] - nums[a])\n",
    "            a += 1\n",
    "            b += 1\n",
    "        return mi\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        min_val = float('inf')\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            cur = nums[i + k - 1] - nums[i]\n",
    "            if cur < min_val:\n",
    "                min_val = cur\n",
    "        return min_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n <2:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for right in range(n-k+1):\n",
    "            ans = min(ans, nums[right + k-1] - nums[right])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        res = inf\n",
    "\n",
    "        for right, x in enumerate(nums[k-1:], k-1):\n",
    "            left = right-k+1\n",
    "            res = min(res, x-nums[left])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        res = inf\n",
    "        nums.sort()\n",
    "        for i in range(k - 1, len(nums)):\n",
    "            res = min(res, nums[i] - nums[i - k + 1]) \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        # left=0\n",
    "        # right=k-1\n",
    "        n=len(nums)\n",
    "        ans=float(\"inf\")\n",
    "        # i的取值范围就在 i,到 i+k-1的范围。从 i 开始连续 k个数\n",
    "        for i in range(n-k+1):\n",
    "            diff=nums[i+k-1]-nums[i]\n",
    "            ans=min(ans,diff)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 100000\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            ans = min(ans, nums[i + k - 1] - nums[i])\n",
    "            if not ans: return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = inf\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            # print(i + k, i)\n",
    "            res = min(res, nums[i + k - 1] - nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        n = len(nums)\n",
    "        res = float('inf')\n",
    "        for i in range(n-k+1):\n",
    "            res = min(res, nums[i]-nums[i+k-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import inf\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        ans = inf\n",
    "        #right=k -1\n",
    "        nums.sort()\n",
    "        if k ==1  or len(nums) == 0:\n",
    "            return 0\n",
    "        for right in range(k-1,len(nums)):\n",
    "            ans = min(ans,nums[right] -nums[left])\n",
    "            left  +=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        nums_len = len(nums)\n",
    "        date_list = []\n",
    "        date_min = 999999\n",
    "        for i in range(0, nums_len - k + 1):\n",
    "            date_list = nums[i:i + k:]\n",
    "            date_min = min(date_min, date_list[-1] - date_list[0])\n",
    "\n",
    "\n",
    "        return date_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        return min(s[i + k - 1] - s[i] for i in range(len(s) - k + 1)) if k > 1 and (s := sorted(nums)) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        k -= 1\n",
    "        fh = float('inf')\n",
    "        for i in range(len(nums)-k):\n",
    "            fh = min(fh, nums[i+k]-nums[i])\n",
    "        return fh\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        # min_value=float('inf')\n",
    "        # for i in range(k-1,len(nums)):\n",
    "        #     min_value = min(max(nums[i-k+1:i+1])-min(nums[i-k+1:i+1]), min_value)\n",
    "\n",
    "        # return min_value\n",
    "        return min([nums[i]-nums[i-k+1] for i in range(k-1,len(nums))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        m=n//3\n",
    "        pre=[]\n",
    "        for i in range(m):\n",
    "            pre.append(-nums[i])\n",
    "        suffix=nums[2*m:]\n",
    "        heapq.heapify(pre)\n",
    "        heapq.heapify(suffix)\n",
    "        mid=nums[m:2*m]\n",
    "        preadd=[0]*(m+1)\n",
    "        preadd[0]=-sum(pre)\n",
    "        #print(preadd)\n",
    "        #print(pre,suffix)\n",
    "        #print(mid)\n",
    "        for i in range(m):\n",
    "            if mid[i]>=-pre[0]:\n",
    "                preadd[i+1]=preadd[i]\n",
    "            else:\n",
    "                preadd[i+1]=preadd[i]+mid[i]+pre[0]\n",
    "                heapq.heappop(pre)\n",
    "                heapq.heappush(pre,-mid[i])\n",
    "        #print(preadd)\n",
    "        suffixadd=sum(suffix)\n",
    "        ans=preadd[-1]-suffixadd\n",
    "        #print(ans)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            if mid[i]<=suffix[0]:\n",
    "                continue\n",
    "            else:\n",
    "                suffixadd+=mid[i]-suffix[0]\n",
    "                heapq.heappop(suffix)\n",
    "                heapq.heappush(suffix, mid[i])\n",
    "                ans=min(ans,preadd[i]-suffixadd)\n",
    "                #print(i,preadd[i],suffix,suffixadd)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m, n = len(nums), len(nums) // 3\n",
    "        left = [inf] * n\n",
    "        tmp = [-num for num in nums[:n]]\n",
    "        s = -sum(tmp)\n",
    "        ans = 2*s - sum(nums[:2*n])\n",
    "        #print(ans)\n",
    "        heapq.heapify(tmp)\n",
    "        for i in range(n, 2 * n):\n",
    "            cur = heapq.heappop(tmp)\n",
    "            s += cur + nums[i]\n",
    "            heapq.heappush(tmp, -nums[i])\n",
    "            left[i - n] = min(left[i - n - 1] if i - n - 1 >= 0 else inf, s)\n",
    "        \n",
    "        right = [-inf] * n\n",
    "        tmp = nums[2*n:]\n",
    "        heapq.heapify(tmp)\n",
    "        s = sum(tmp)\n",
    "        ans = min(ans, left[-1] - s)\n",
    "        #print(ans)\n",
    "        for i in range(-n - 1, -2*n - 1, -1):\n",
    "            cur = heapq.heappop(tmp)\n",
    "            s += nums[i] - cur\n",
    "            heapq.heappush(tmp, nums[i])\n",
    "            right[i + 2*n] = max(right[i + 2*n + 1] if i + 2*n + 1 < n else -inf, s)\n",
    "        ans = min(ans, sum(nums[:n]) - right[0])\n",
    "        for i in range(n - 1):\n",
    "            ans = min(ans, left[i] - right[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m, n = len(nums), len(nums) // 3\n",
    "        tmp = [-nums[i] for i in range(n)]\n",
    "        s = -sum(tmp)\n",
    "        left = [s] * (n + 1)\n",
    "        heapq.heapify(tmp)\n",
    "        for i in range(n, 2*n):\n",
    "            cur = heapq.heappop(tmp)\n",
    "            s += cur + nums[i]\n",
    "            left[i - n + 1] = min(left[i - n], s)\n",
    "            heapq.heappush(tmp, -nums[i])\n",
    "        \n",
    "        tmp = [nums[i] for i in range(2*n, m)]\n",
    "        s = sum(tmp)\n",
    "        heapq.heapify(tmp)\n",
    "        right = [s] * (n + 1)\n",
    "        for i in range(-n-1, -2*n-1, -1):\n",
    "            cur = heapq.heappop(tmp)\n",
    "            s += nums[i] - cur\n",
    "            right[i + 2*n] = max(right[i+2*n + 1], s)\n",
    "            heapq.heappush(tmp, nums[i])\n",
    "        #print(left, right)\n",
    "        ans = inf\n",
    "        for i in range(n + 1):\n",
    "            ans = min(ans, left[i] - right[i])    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        n3, n = len(nums), len(nums) // 3\n",
    "\n",
    "        part1 = [0] * ( n + 1)\n",
    "\n",
    "        total = sum(nums[:n])\n",
    "\n",
    "        ql = [-x for x in nums[:n]]\n",
    "\n",
    "        heapq.heapify(ql)\n",
    "        part1[0] = total\n",
    "\n",
    "        for i in range(n, n * 2):\n",
    "\n",
    "            total += nums[i]\n",
    "            heapq.heappush(ql, - nums[i])\n",
    "            total -= - heapq.heappop(ql)\n",
    "            part1[i - (n - 1)] = total\n",
    "\n",
    "        part2 = sum(nums[n * 2 :])\n",
    "\n",
    "        qr = nums[n * 2:]\n",
    "        heapq.heapify(qr)\n",
    "        ans = part1[n] - part2\n",
    "        for i in range(n * 2 - 1, n - 1, -1):\n",
    "            part2 += nums[i]\n",
    "            heapq.heappush(qr, nums[i])\n",
    "            part2 -= heapq.heappop(qr)\n",
    "            ans = min(ans, part1[i - n] - part2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        n3, n = len(nums), len(nums) // 3\n",
    "\n",
    "        part1 = [0] * ( n + 1)\n",
    "\n",
    "        total = sum(nums[:n])\n",
    "\n",
    "        ql = [-x for x in nums[:n]]\n",
    "\n",
    "        heapq.heapify(ql)\n",
    "        part1[0] = total\n",
    "\n",
    "        for i in range(n, n * 2):\n",
    "\n",
    "            total += nums[i]\n",
    "            heapq.heappush(ql, - nums[i])\n",
    "            total -= - heapq.heappop(ql)\n",
    "            part1[i - (n - 1)] = total\n",
    "\n",
    "        part2 = sum(nums[n * 2 :])\n",
    "\n",
    "        qr = nums[n * 2:]\n",
    "        heapq.heapify(qr)\n",
    "        ans = part1[n] - part2\n",
    "        for i in range(n * 2 - 1, n - 1, -1):\n",
    "            part2 += nums[i]\n",
    "            heapq.heappush(qr, nums[i])\n",
    "            part2 -= heapq.heappop(qr)\n",
    "            ans = min(ans, part1[i - n] - part2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 3\n",
    "        first = [-x for x in nums[:n]]\n",
    "        heapify(first)\n",
    "        total = sum(first)\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = total\n",
    "        for i in range(n, 2*n):\n",
    "            total += -nums[i]\n",
    "            heappush(first, -nums[i])\n",
    "            x = heappop(first)\n",
    "            total -= x\n",
    "            dp[i - n + 1] = total\n",
    "    \n",
    "        second = [x for x in nums[-n:]]\n",
    "        total = sum(second)\n",
    "        heapify(second)\n",
    "        ret = -dp[n] - total\n",
    "        for i in range(2 * n - 1, n - 1, -1):\n",
    "            total += nums[i]\n",
    "            heappush(second, nums[i])\n",
    "            x = heappop(second)\n",
    "            total -= x\n",
    "            ret = min(ret, -dp[i - n] - total)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "\n",
    "        # iterates over split point i in range [n, 2n]\n",
    "\n",
    "        # 1. preMin[i]: min sum of n numbers among the first i numbers\n",
    "        maxHeap = [-num for num in nums[:n]]\n",
    "        heapify(maxHeap)\n",
    "        preMin = [0] * (n+1)\n",
    "        preMin[0] = total = -sum(maxHeap)\n",
    "        \n",
    "        for i in range(n, 2*n):\n",
    "            total += nums[i] + heappushpop(maxHeap, -nums[i])\n",
    "            preMin[i - (n-1)] = total\n",
    "            \n",
    "        # 2. sufMax[i]: max sum of n numbers among the last i numbers\n",
    "        minHeap = nums[-n:]\n",
    "        heapify(minHeap)\n",
    "        sufMax = sum(minHeap) \n",
    "        ans = preMin[n] - sufMax\n",
    "        for i in range(2*n-1, n-1, -1):\n",
    "            sufMax += nums[i] - heappushpop(minHeap, nums[i])\n",
    "\n",
    "            ans = min(ans, preMin[i-n] - sufMax)\n",
    "\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # first尽可能小\n",
    "        first = []\n",
    "        sum_first = 0\n",
    "        for c in nums[:n // 3]:\n",
    "            heappush(first, -c)\n",
    "            sum_first += c\n",
    "        dp_first = [sum_first]\n",
    "        for c in nums[n // 3: -n // 3]:\n",
    "            if c < -first[0]:\n",
    "                sum_first += c - (-heapreplace(first, -c))\n",
    "            dp_first.append(sum_first)\n",
    "        \n",
    "        # second尽可能大\n",
    "        second = []\n",
    "        sum_second = 0\n",
    "        for c in nums[-n // 3:]:\n",
    "            heappush(second, c)\n",
    "            sum_second += c\n",
    "        dp_second = [sum_second]\n",
    "        for c in reversed(nums[n // 3: -n // 3]):\n",
    "            if c > second[0]:\n",
    "                sum_second += c - heapreplace(second, c)\n",
    "            dp_second.append(sum_second)\n",
    "        \n",
    "        # print(first, second)\n",
    "        # print(dp_first, dp_second)\n",
    "        return min(a - b for a, b in zip(dp_first, dp_second[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)//3\n",
    "        pq = [-x for x in nums[:n]]     \n",
    "        total = sum(nums[:n])\n",
    "        heapq.heapify(pq)\n",
    "        part1 = [total]\n",
    "        for i in range(n, 2*n):        \n",
    "            total += nums[i]\n",
    "            total -= -heapq.heappushpop(pq, -nums[i])   \n",
    "            part1.append(total)\n",
    "        pq = nums[2*n:]\n",
    "        total = sum(nums[2*n:])\n",
    "        heapq.heapify(pq)\n",
    "        part2 = [total]\n",
    "        for i in range(2*n-1, n-1, -1): \n",
    "            total += nums[i]\n",
    "            total -= heapq.heappushpop(pq, nums[i])     \n",
    "            part2.append(total)\n",
    "        ans = float('inf')\n",
    "        for i in range(n+1):\n",
    "            ans = min(ans, part1[i] - part2[n-i])        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq \n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)//3\n",
    "\n",
    "        stack1 = [-x for x in nums[:n]]\n",
    "        \n",
    "        min_val = -sum(stack1)\n",
    "        heapq.heapify(stack1)\n",
    "        left = [0]*(3*n)\n",
    "        left[n-1] = min_val\n",
    "        for i in range(n,2*n):\n",
    "            x = nums[i]\n",
    "            if stack1[0]>=-x:\n",
    "                left[i] = min_val\n",
    "                continue\n",
    "            else:\n",
    "                y = heapq.heappop(stack1)\n",
    "             \n",
    "                heapq.heappush(stack1,-x)\n",
    "         \n",
    "                min_val = min_val+y+x\n",
    "                left[i] = min_val\n",
    "        \n",
    "\n",
    "        stack2 = [x for x in nums[2*n:]]\n",
    "        #print(stack2,\"2\")\n",
    "        max_val = sum(stack2)\n",
    "        heapq.heapify(stack2)\n",
    "\n",
    "        right = [0]*(3*n)\n",
    "        right[2*n] = max_val \n",
    "\n",
    "        for i in range(2*n-1,n-1,-1):\n",
    "            x = nums[i]\n",
    "            if x<=stack2[0]:\n",
    "                right[i] = max_val\n",
    "                continue\n",
    "            y = heapq.heappop(stack2)\n",
    "            heapq.heappush(stack2,x)\n",
    "            max_val = max_val-y+x\n",
    "            right[i] = max_val\n",
    "        \n",
    "        #print(left)\n",
    "        #print(right)\n",
    "        min_ans = float(\"inf\")\n",
    "        for i in range(n-1,2*n):\n",
    "            min_ans = min(min_ans, left[i]-right[i+1] )\n",
    "        return min_ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq \n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)//3\n",
    "\n",
    "        stack1 = [-x for x in nums[:n]]\n",
    "        \n",
    "        min_val = -sum(stack1)\n",
    "        heapq.heapify(stack1)\n",
    "        left = [0]*(3*n)\n",
    "        left[n-1] = min_val\n",
    "        for i in range(n,2*n):\n",
    "            x = nums[i]\n",
    "            if stack1[0]>=-x:\n",
    "                left[i] = min_val\n",
    "                continue\n",
    "            else:\n",
    "                y = heapq.heappop(stack1)\n",
    "             \n",
    "                heapq.heappush(stack1,-x)\n",
    "         \n",
    "                min_val = min_val+y+x\n",
    "                left[i] = min_val\n",
    "        \n",
    "\n",
    "        stack2 = [x for x in nums[2*n:]]\n",
    "        print(stack2,\"2\")\n",
    "        max_val = sum(stack2)\n",
    "        heapq.heapify(stack2)\n",
    "\n",
    "        right = [0]*(3*n)\n",
    "        right[2*n] = max_val \n",
    "\n",
    "        for i in range(2*n-1,n-1,-1):\n",
    "            x = nums[i]\n",
    "            if x<=stack2[0]:\n",
    "                right[i] = max_val\n",
    "                continue\n",
    "            y = heapq.heappop(stack2)\n",
    "            heapq.heappush(stack2,x)\n",
    "            max_val = max_val-y+x\n",
    "            right[i] = max_val\n",
    "        \n",
    "        #print(left)\n",
    "        #print(right)\n",
    "        min_ans = float(\"inf\")\n",
    "        for i in range(n-1,2*n):\n",
    "            min_ans = min(min_ans, left[i]-right[i+1] )\n",
    "        return min_ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\r\n",
    "        m = len(nums)\r\n",
    "        n = m // 3\r\n",
    "\r\n",
    "        min_pq = nums[-n:]\r\n",
    "        heapify(min_pq)\r\n",
    "        suf_max = [0] * (m - n + 1)  # 后缀最大和\r\n",
    "        suf_max[-1] = s = sum(min_pq)\r\n",
    "        for i in range(m - n - 1, n - 1, -1):\r\n",
    "            s += nums[i] - heappushpop(min_pq, nums[i])\r\n",
    "            suf_max[i] = s\r\n",
    "\r\n",
    "        max_pq = [-v for v in nums[:n]]  # 所有元素取反当最大堆\r\n",
    "        heapify(max_pq)\r\n",
    "        pre_min = -sum(max_pq)  # 前缀最小和\r\n",
    "        ans = pre_min - suf_max[n]\r\n",
    "        for i in range(n, m - n):\r\n",
    "            pre_min += nums[i] + heappushpop(max_pq, -nums[i])\r\n",
    "            ans = min(ans, pre_min - suf_max[i + 1])\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "        suf_max = [0] * (m - n + 1)\n",
    "        pq = nums[-n:]\n",
    "        heapify(pq)\n",
    "        suf_max[-1] = s = sum(pq)\n",
    "        for i in range(m - n - 1, n - 1, -1):\n",
    "            s += nums[i] - heappushpop(pq, nums[i])\n",
    "            suf_max[i] = s\n",
    "        pq = [-nums[i] for i in range(n)]\n",
    "        pre_min = -sum(pq)\n",
    "        heapify(pq)\n",
    "        ans = pre_min - suf_max[n]\n",
    "        for i in range(n, m - n):\n",
    "            pre_min += nums[i] + heappushpop(pq, -nums[i])\n",
    "            ans = min(ans, pre_min - suf_max[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "\n",
    "        min_pq = nums[-n:] \n",
    "        heapify(min_pq)\n",
    "        suf_max = [0] * (m - n + 1) # 后缀最大和\n",
    "        suf_max[-1] = s = sum(min_pq)\n",
    "        for i in range(m - n - 1, n - 1, -1):\n",
    "            s += nums[i] - heappushpop(min_pq, nums[i])\n",
    "            suf_max[i] = s\n",
    "        \n",
    "        max_pq = [-v for v in nums[:n]] # 所有元素取反当最大堆\n",
    "        heapify(max_pq)\n",
    "        pre_min = -sum(max_pq) # 前缀最小和\n",
    "        ans = pre_min - suf_max[n]\n",
    "        for i in range(n, m - n):\n",
    "            pre_min += nums[i] + heappushpop(max_pq, -nums[i])\n",
    "            ans = min(ans, pre_min - suf_max[i + 1])\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#选最大的后n个和最小的前n个\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "\n",
    "        min_pq = nums[-n:]\n",
    "        heapify(min_pq)\n",
    "        suf_max = [0] * (m - n + 1) \n",
    "        suf_max[-1] = s = sum(min_pq)\n",
    "        for i in range(m - n - 1, n - 1, -1):\n",
    "            s += nums[i] - heappushpop(min_pq, nums[i])\n",
    "            suf_max[i] = s\n",
    "\n",
    "        max_pq = [-v for v in nums[:n]] \n",
    "        heapify(max_pq)\n",
    "        pre_min = -sum(max_pq) \n",
    "        ans = pre_min - suf_max[n]\n",
    "        for i in range(n, m - n):\n",
    "            pre_min += nums[i] + heappushpop(max_pq, -nums[i])\n",
    "            ans = min(ans, pre_min - suf_max[i + 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        # 将数组分为3份，删除一份，另两份求和之差最小\n",
    "        # 优先队列\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "\n",
    "        min_pq = nums[-n:] # 最小堆\n",
    "        heapify(min_pq)\n",
    "        suf_max = [0] * (m - n + 1) # 后缀最大和\n",
    "        suf_max[-1] = s = sum(min_pq)\n",
    "        for i in range(m - n - 1, n - 1, -1): # 元素遍历计后缀最大和\n",
    "            s += nums[i] - heappushpop(min_pq, nums[i])\n",
    "            suf_max[i] = s\n",
    "        \n",
    "        max_pq = [-v for v in nums[:n]] # 所有元素取反当最大堆\n",
    "        heapify(max_pq)\n",
    "        pre_min = -sum(max_pq) # 前缀最小和\n",
    "        ans = pre_min - suf_max[n]\n",
    "        for i in range(n, m - n):\n",
    "            pre_min += nums[i] + heappushpop(max_pq, -nums[i]) # 前缀最小和\n",
    "            ans = min(ans, pre_min - suf_max[i + 1])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        import heapq\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "        \n",
    "        min_pq = nums[-n:]\n",
    "        heapq.heapify(min_pq)\n",
    "        suf_max = [0] * (m - n + 1)\n",
    "        suf_max[-1] = s = sum(min_pq)\n",
    "        for i in range(m - n - 1, n - 1, -1):\n",
    "            s += nums[i] - heapq.heappushpop(min_pq, nums[i])\n",
    "            suf_max[i] = s\n",
    "        \n",
    "        max_pq = [-x for x in nums[:n]]\n",
    "        heapq.heapify(max_pq)\n",
    "        pre_min = -sum(max_pq)\n",
    "        ans = pre_min - suf_max[n]\n",
    "        for i in range(n, m - n):\n",
    "            pre_min += nums[i] + heapq.heappushpop(max_pq, -nums[i])\n",
    "            ans = min(ans, pre_min - suf_max[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "        min_pq = nums[-n:]\n",
    "        heapify(min_pq)\n",
    "        suf_max = [0] * (m - n + 1)\n",
    "        suf_max[-1] = s = sum(min_pq)\n",
    "        for i in range(m - n - 1, n - 1, -1):\n",
    "            s += nums[i] - heappushpop(min_pq, nums[i])\n",
    "            suf_max[i] = s\n",
    "        max_pq = [-v for v in nums[:n]]\n",
    "        heapify(max_pq)\n",
    "        pre_min = -sum(max_pq)\n",
    "        ans = pre_min - suf_max[n]\n",
    "        for i in range(n, m - n) :\n",
    "            pre_min += nums[i] + heappushpop(max_pq, -nums[i])\n",
    "            ans = min(ans, pre_min - suf_max[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m//3\n",
    "        min_pq = nums[-n:]\n",
    "        heapify(min_pq)\n",
    "        sufMax = [0] * (2*n+1)\n",
    "        sufMax[-1] = sum(min_pq)\n",
    "        s = sufMax[-1]\n",
    "        for i in range(m-n-1,n-1,-1):\n",
    "            s += nums[i] - heappushpop(min_pq,nums[i])\n",
    "            sufMax[i] = s\n",
    "\n",
    "        \n",
    "        max_pq = [-v for v in nums[:n]]\n",
    "        heapify(max_pq)\n",
    "        preMin = -sum(max_pq)\n",
    "        ans = preMin - sufMax[n]\n",
    "        for i in range(n,m-n):\n",
    "            preMin += nums[i] + heappushpop(max_pq, -nums[i])\n",
    "            ans = min(ans, preMin - sufMax[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m=len(nums)\n",
    "        n=m//3\n",
    "        sur_sum=0\n",
    "        pq1=PriorityQueue()#默认小顶堆\n",
    "        for i in range(m-1, m-n-1,-1):\n",
    "            sur_sum+=nums[i]\n",
    "            pq1.put(nums[i])\n",
    "        sur_list=[0 for _ in range(2*n+1)]\n",
    "        sur_list[-1]=sur_sum\n",
    "        for i in range(m-n-1, n-1,-1):\n",
    "            pq1.put(nums[i])\n",
    "            sur_sum=sur_sum-pq1.get()+nums[i]\n",
    "            sur_list[i]=sur_sum\n",
    "        pq1=PriorityQueue()\n",
    "        pre_sum=0\n",
    "        for i in range(n):\n",
    "            pre_sum+=nums[i]\n",
    "            pq1.put(-nums[i])\n",
    "\n",
    "        ans=pre_sum-sur_list[n]\n",
    "        for i in range(n, m-n):\n",
    "            pq1.put(-nums[i])\n",
    "            pre_sum=pre_sum+pq1.get()+nums[i]\n",
    "            ans=min(ans, pre_sum-sur_list[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 3\n",
    "        left, right = [0] * (n + 1), [0] * (n + 1) # left[i]表示左半段元素个数为n + i时的n个最小和，right[i]表示右半段元素个数为n + i时的最大和\n",
    "        ql, qr, l, r = [], [], 0, 0\n",
    "        for i in range(2 * n):\n",
    "            heapq.heappush(ql, -nums[i])\n",
    "            heapq.heappush(qr, nums[3 * n - 1 - i])\n",
    "            l += nums[i]\n",
    "            r += nums[3 * n - 1 - i]\n",
    "            if len(ql) > n:\n",
    "                l += heapq.heappop(ql)\n",
    "            if len(qr) > n:\n",
    "                r -= heapq.heappop(qr)\n",
    "            if i >= n - 1:\n",
    "                left[i - (n - 1)] = l\n",
    "                right[i - (n - 1)] = r\n",
    "        return min(left[i] - right[n - i] for i in range(n + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 3\n",
    "        f = [0] * len(nums)\n",
    "        h = []\n",
    "        for i in range(n * 2):\n",
    "            f[i] = (f[i - 1] if i else 0) + nums[i]\n",
    "            heappush(h, -nums[i])\n",
    "            if len(h) > n:\n",
    "                f[i] += heappop(h)\n",
    "        ans = 10**10\n",
    "        lst = 0\n",
    "        h = []\n",
    "        for i in range(n * 3 - 1, n - 1, -1):\n",
    "            lst += nums[i]\n",
    "            heappush(h, nums[i])\n",
    "            if len(h) > n:\n",
    "                lst -= heappop(h)\n",
    "            if i <= n * 2:\n",
    "                ans = min(ans, f[i - 1] - lst)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m=len(nums)\n",
    "        n=m//3\n",
    "        h1=[]\n",
    "        s=0\n",
    "        pre=[inf]*m\n",
    "        for i in range(2*n):\n",
    "            heappush(h1,-nums[i])\n",
    "            s+=nums[i]\n",
    "            if i>=n-1:\n",
    "                if i-1>=0:\n",
    "                    pre[i]=min(pre[i-1],s)\n",
    "                else:\n",
    "                    pre[i]=s\n",
    "                s+=heappop(h1)\n",
    "        \n",
    "        suf=[-inf]*m\n",
    "        h2=[]\n",
    "        s=0\n",
    "\n",
    "        for i in range(m-1,n-1,-1):\n",
    "            heappush(h2,nums[i])\n",
    "            s+=nums[i]\n",
    "            if i<=2*n:\n",
    "                if i+1<m:\n",
    "                    suf[i]=max(suf[i+1],s)\n",
    "                else:\n",
    "                    suf[i]=s\n",
    "                s-=heappop(h2)\n",
    "        print(pre,suf)\n",
    "\n",
    "        res=inf\n",
    "        for i in range(n-1,2*n):\n",
    "            res=min(res,pre[i]-suf[i+1])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n3, n = len(nums), len(nums) // 3\n",
    "\n",
    "        front_list = [-v for v in nums[:n]]\n",
    "        heapq.heapify(front_list)\n",
    "        front_sum = -sum(front_list)\n",
    "        front_min_sums = [front_sum]\n",
    "        for i in range(n, 2 * n):\n",
    "            heapq.heappush(front_list, -nums[i])\n",
    "            pop_v = heapq.heappop(front_list)\n",
    "            front_sum = front_sum + nums[i] + pop_v\n",
    "            front_min_sums.append(front_sum)\n",
    "\n",
    "        rear_list = nums[2*n:]\n",
    "        heapq.heapify(rear_list)\n",
    "        rear_sum = sum(rear_list)\n",
    "        rear_max_sums = [rear_sum]\n",
    "        for i in range(2 * n - 1, n - 1, -1):\n",
    "            heapq.heappush(rear_list, nums[i])\n",
    "            pop_v = heapq.heappop(rear_list)\n",
    "            rear_sum = rear_sum - pop_v +  nums[i]\n",
    "            rear_max_sums.append(rear_sum)\n",
    "        rear_max_sums = rear_max_sums[::-1]\n",
    "        \n",
    "        ans = sys.maxsize\n",
    "        for i in range(len(front_min_sums)):\n",
    "            ans = min(ans, front_min_sums[i] - rear_max_sums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = n // 3\n",
    "        sufs = [0] * n\n",
    "        s = 0\n",
    "        queue = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            num = nums[i]\n",
    "            s += num\n",
    "            heapq.heappush(queue,num)\n",
    "            if len(queue) > m:\n",
    "                s -= heapq.heappop(queue)\n",
    "            sufs[i] = s\n",
    "        \n",
    "        s = 0\n",
    "        queue = []\n",
    "        ans = inf\n",
    "        for i , num in enumerate(nums):\n",
    "            if i == n - m:break\n",
    "            s += num\n",
    "            heapq.heappush(queue,-num)\n",
    "            if len(queue) > m:\n",
    "                s += heapq.heappop(queue)\n",
    "            if i >= m-1:\n",
    "                ans = min(ans,s - sufs[i+1])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)//3\n",
    "        pre = [inf]*(3*n+1)\n",
    "        stack = []\n",
    "        s = 0\n",
    "        for i in range(3*n):\n",
    "            s += nums[i]\n",
    "            heappush(stack, -nums[i])\n",
    "            if len(stack) > n:\n",
    "                s += heappop(stack)\n",
    "            if len(stack) == n:\n",
    "                pre[i+1] = s\n",
    "\n",
    "        post = [-inf] * (3*n + 1)\n",
    "        stack = []\n",
    "        s = 0\n",
    "        for i in range(3 * n-1, -1, -1):\n",
    "            s += nums[i]\n",
    "            heappush(stack, nums[i])\n",
    "            if len(stack) > n:\n",
    "                s -= heappop(stack)\n",
    "            if len(stack) == n:\n",
    "                post[i] = s\n",
    "        return min(pre[i+1] - post[i+1] for i in range(3*n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 3\n",
    "        hMax1 = [-nums[i] for i in range(n)]\n",
    "        hMin2 = nums[-n:]\n",
    "        heapify(hMax1)\n",
    "        heapify(hMin2)\n",
    "        min2s = [0]*(n+1)\n",
    "        max1s = [0]*(n+1)\n",
    "        total = sum(nums)\n",
    "        accu = list(islice(accumulate(nums), n-1, n*2))\n",
    "        for i in range(n):\n",
    "            heappush(hMax1, -nums[i+n])\n",
    "            max1s[i+1] = max1s[i] + heappop(hMax1)\n",
    "            heappush(hMin2, nums[-n - 1 - i])\n",
    "            min2s[i+1] = min2s[i] + heappop(hMin2)\n",
    "        _min = min(accu[i]*2 + max1s[i] + min2s[n-i] for i in range(n+1))\n",
    "        return _min - total\n",
    "            \n",
    "\n",
    "        # A[k] = S1 + x for i in range(n+1):\n",
    "\n",
    "        # A[k] = S1 + x\n",
    "        # A - A[k] = y + S2\n",
    "        # 2A[k] - A = S1 - S2 + x - y\n",
    "        # S1 - S2 = 2A[k] - A + y - x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "        \n",
    "        pre = [0] * m\n",
    "        h_max = []\n",
    "        pre[0] = nums[0]\n",
    "        heappush(h_max, -nums[0])\n",
    "        for i in range(1, m) :\n",
    "            if i < n :\n",
    "                heappush(h_max, -nums[i])\n",
    "                pre[i] = pre[i-1] + nums[i]\n",
    "            else :\n",
    "                tmp = pre[i-1]\n",
    "                if nums[i] < -h_max[0] :\n",
    "                    tmp += heappop(h_max) + nums[i]\n",
    "                    heappush(h_max, -nums[i])\n",
    "                pre[i] = tmp\n",
    "        \n",
    "        suf = [0] * m\n",
    "        h_min = []\n",
    "        suf[-1] = nums[-1]\n",
    "        heappush(h_min, nums[-1])\n",
    "        for i in range(m-2, -1, -1) :\n",
    "            if i >= 2*n :\n",
    "                heappush(h_min, nums[i])\n",
    "                suf[i] = suf[i+1] + nums[i]\n",
    "            else :\n",
    "                tmp = suf[i+1]\n",
    "                if nums[i] > h_min[0] :\n",
    "                    tmp += -heappop(h_min) + nums[i]\n",
    "                    heappush(h_min, nums[i])\n",
    "                suf[i] = tmp\n",
    "        ans = inf\n",
    "        for i in range(n-1, m-n) :\n",
    "            ans = min(ans, pre[i]-suf[i+1])\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "\n",
    "        s = 0\n",
    "        pre = [0] * (m + 1)\n",
    "        q1 = []\n",
    "        for i, x in enumerate(nums[: n * 2], 1):\n",
    "            s += x\n",
    "            heappush(q1, -x)\n",
    "            if len(q1) > n:\n",
    "                s -= -heappop(q1)\n",
    "            pre[i] = s\n",
    "\n",
    "        s = 0\n",
    "        suf = [0] * (m + 1)\n",
    "        q2 = []\n",
    "        for i in range(m, n, -1):\n",
    "            x = nums[i - 1]\n",
    "            s += x\n",
    "            heappush(q2, x)\n",
    "            if len(q2) > n:\n",
    "                s -= heappop(q2)\n",
    "            suf[i] = s\n",
    "        \n",
    "        return min(pre[i] - suf[i + 1] for i in range(n, n * 2 + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 3\n",
    "\n",
    "        s = 0\n",
    "        pre = [0] * (m + 1)\n",
    "        q1 = []\n",
    "        for i, x in enumerate(nums[: n * 2], 1):\n",
    "            s += x\n",
    "            heappush(q1, -x)\n",
    "            if len(q1) > n:\n",
    "                s -= -heappop(q1)\n",
    "            pre[i] = s\n",
    "\n",
    "        s = 0\n",
    "        suf = [0] * (m + 1)\n",
    "        q2 = []\n",
    "        for i in range(m, n, -1):\n",
    "            x = nums[i - 1]\n",
    "            s += x\n",
    "            heappush(q2, x)\n",
    "            if len(q2) > n:\n",
    "                s -= heappop(q2)\n",
    "            suf[i] = s\n",
    "        \n",
    "        return min(pre[i] - suf[i + 1] for i in range(n, n * 2 + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        # 遍历所有切割点就可以了吧 n ~ 2 n    最小化左侧，最大化右侧，就是答案\n",
    "        # 问题是如果高效计算和\n",
    "        # 前后缀分解能解决问题\n",
    "        from sortedcontainers import SortedList\n",
    "        \n",
    "        n = len(nums) // 3\n",
    "        left = defaultdict(int)\n",
    "        right =  defaultdict(int)\n",
    "        \n",
    "        # 处理左边的情况\n",
    "        s = sum(nums[i] for i in range(n))\n",
    "        left[n-1] = s\n",
    "        h = []\n",
    "        for i in range(n):\n",
    "            heappush(h, -nums[i])\n",
    "        for i in range(n, 2*n):\n",
    "            top = -h[0]\n",
    "            if top > nums[i]:\n",
    "                s = s - top +nums[i]\n",
    "                heappop(h)\n",
    "                heappush(h, -nums[i])\n",
    "            left[i] = s\n",
    "        \n",
    "        # 处理右边的情况\n",
    "        s = sum(nums[i] for i in range(2*n, 3*n))\n",
    "        right[2*n] = s\n",
    "        h = []\n",
    "        for i in range(n):\n",
    "            heappush(h, nums[2*n+i])\n",
    "        for i in range(n):\n",
    "            top = h[0]\n",
    "            x = nums[2*n-i-1]\n",
    "            if x > top:\n",
    "                s = s + x - top\n",
    "                heappop(h)\n",
    "                heappush(h, x)\n",
    "            right[2*n-i-1] = s\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n-1, 2*n):\n",
    "            ans = min(ans, left[i] - right[i+1])\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "        \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minimumDifference(self, a: List[int]) -> int:\n",
    "        def f(x):\n",
    "            n = len(x)//3\n",
    "            st = SortedList(x[:n])\n",
    "            pre = sum(x[:n])\n",
    "            dic = {n-1:pre}\n",
    "            for j in range(n, n*2):\n",
    "                if x[j]>=st[-1]:\n",
    "                    pass \n",
    "                else:\n",
    "                    pre -= st[-1]\n",
    "                    st.remove(st[-1])\n",
    "                    st.add(x[j])\n",
    "                    pre += x[j]\n",
    "                dic[j] = pre\n",
    "            return dic \n",
    "        \n",
    "        def g(x):\n",
    "            n = len(x)//3\n",
    "            st = SortedList(x[:n])\n",
    "            pre = sum(x[:n])\n",
    "            dic = {n-1:pre}\n",
    "            for j in range(n, n*2):\n",
    "                if x[j]<=st[0]:\n",
    "                    pass \n",
    "                else:\n",
    "                    pre -= st[0]\n",
    "                    st.remove(st[0])\n",
    "                    st.add(x[j])\n",
    "                    pre += x[j]\n",
    "                dic[j] = pre\n",
    "            return dic\n",
    "        b = f(a)\n",
    "        c = g(a[::-1])\n",
    "        n = len(a)//3\n",
    "        ans = float('inf')\n",
    "        for j in range(n-1, n*2):\n",
    "            ans = min(ans, b[j] - c[3*n-1-(j+1)])\n",
    "        return ans \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 3\n",
    "        pq1 = [-x for x in nums[:n]]\n",
    "        pq2 = nums[2*n:]\n",
    "        heapq.heapify(pq1)\n",
    "        heapq.heapify(pq2)\n",
    "        mark = [[0,0] for _ in range(n+1)]\n",
    "        s1 = -sum(pq1)\n",
    "        s2 = sum(pq2)\n",
    "        mark[0][0] = s1\n",
    "        mark[-1][1] = s2\n",
    "        for i in range(n):\n",
    "            a1 = heapq.heappushpop(pq1, -nums[i+n])\n",
    "            mark[i+1][0] = mark[i][0] +a1 + nums[i+n]\n",
    "            a2 = heapq.heappushpop(pq2, nums[2*n-1-i])\n",
    "            mark[n-1-i][1] = mark[n-i][1] - a2 + nums[2*n-1-i]\n",
    "        s = [a-b for a,b in mark]\n",
    "        return min(s)\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
